1. Field of the Invention
This invention relates to a method and apparatus for decoding convolutionally encoded signals. Such signals are commonly used in communications and recording systems that employ error correction to combat signal corruption.
2. Description of the Related Art
One increasingly popular redundant coding scheme used in wireless and other types of communications systems is convolutional coding, in which the coding of particular symbol depends upon the value of that symbol and the value of a certain number of symbols preceding and succeeding that particular symbol.
It would be desirable to improve upon conventional maximum likelihood sequence estimation (“MLSE”) decoders such as Viterbi decoders, which are commonly used to decode convolutionally encoded data. If sk is a vector that represents an actual transmitted sequence of symbols and r is a vector that represents the actual signals received by a mobile, a Viterbi decoder effectively tests all of the possible values of sk and selects the Sk that maximizes the summation (“cross correlation”) Σn c[n]r[n]sk[n]=skTCr, where c[n] defines the channel gain for a transmitted symbol for sample n (and thus C is a diagonal matrix with these values). (The sk that maximizes the cross correlation is the sk that minimizes the “distance” between rand sk.) For more details regarding Viterbi decoders, see, for example, “Digital Communications”, John G. Proakis (3-d edition 1995).
The best sk may be represented as a path through nodes in a diagram (known as a trellis), where lines (“transitions”) between nodes in adjacent time steps represent whether an input symbol (information bit) was a 0 or a 1 (for binary coding). The nodes (“states”) in vertical columns represent the values of prior input symbols. A “path” through the trellis therefore represents a particular sequence of input symbols. FIG. 1 shows an example of a trellis with only two paths shown. The time steps indicate a decoder trellis beginning at time t=0 to time t=. At each time step, the decision units of the decoder contain the value of the cross correlation of the most likely path to the state of interest. Thus, the decoder trellis contains multiple paths from an initial state to a given state several time steps later.
However, only one path has the highest cross correlation and is the most likely path. The most likely path to a particular state within a given time step is found by starting at that particular state at that given time step and tracing backward (a “raceback”) along the chosen transitions. Information bits that correspond to the transitions along the path are the decoded data. An information bit equal to 0 is shown is a solid line; an information bit equal to 1 is shown as a dotted line. Thus, the path shown in FIG. 1 ending at state A at time t=0 corresponds to an information bit sequence equal to 0100.
A weight is computed for each state at each time, where the weight for a particular state at a particular time corresponds to the likelihood that the encoder was in that state at that time. The weight is equal to the weight of a previous state that transitioned to the current state plus a weight based upon the likelihood of the transition. For example, node 10 at time t=has a metric of four which equals the weight of node 12 at time t=3 plus the weight for the transition between those nodes. The node at any given time with the highest weight is the node that ends the most likely path and is therefore the node from which the traceback will occur.
To achieve good noise performance from the decoding process, the traceback length must generally be several times the constraint length (the number of input bits upon which an output depends; this is the length of a shift register that may be used to perform the encoding) of the code. In current code division multiple access (“CDMA”), a traceback length L=5*K, where K is the constraint length, is frequently taken as the minimum acceptable traceback length.
For a decoder with bits of memory, M−L valid bits can be obtained after each traceback. If an incoming data frame consists of N information bits (assumed to be greater than M), the number of L bit tracebacks is (N−K)/(M−L), which corresponds to a computation requirement of M*(N−K)/(M−L), where a computation is assumed to be a one bit traceback. (The one bit traceback is used simply as a “yardstick.”) If M=L+1, this equation reduces to (L+1)*(N−K), which corresponds to the smallest memory and the greatest computational overhead.
Instead of performing periodic, partial tracebacks, if the decoder memory is sufficiently large, an entire incoming data frame may be stored and a full traceback of length (N−K) performed. Thus the full traceback is less computationally intensive than the periodic traceback scheme by a factor of M/(M−L). However, larger memories (greater M) are costly.
It would be desirable to implement the partial traceback scheme, with its smaller memory requirement, while at the same time decreasing its computational overhead.